public class MySingleList {

    static class Node {
        public int val;
        public Node next;


        public Node(int val) {
            this.val = val;
        }
    }
    public Node head;

        public void createLink(){
            // 四个节点 ，
            Node node1 = new Node(12);
            Node node2 = new Node(45);
            Node node3 = new Node(23);
            Node node4 = new Node(90);

            //给next赋值
            node1.next = node2;
            node2.next = node3;
            node3.next = node4;
            head = node1;
        }


        public void display(Node newHead){
            Node cur = newHead;
            while( /*head != null*/  cur !=  null ){
                System.out.print(cur.val+" ");
                cur = cur.next;
            }
            System.out.println();
        }

        //编写一个代码，给定值x为基准将链表分割成两部分，所有 小于x的节点 排在大于或等于x的其余节点之前,且不能改变原来的数据顺序
        //链表分割
        //遍历一边链表
        // 将其分为大于等于x的一部分， 和小于x的一部分
        //   bs be                 as ae
        // 然后再用尾插法来加新节点 ， 最后再将两个节点拼接起来

        public Node partition(int x){
            Node bs = null;  // 前半部分的头节点
            Node be = null;  // 前半部分的尾节点
            Node as = null;  // 后半部分的头节点
            Node ae = null;  // 后半部分的尾节点

            Node cur = head;
            //遍历链表
            while(cur!=null){
                //将其分为两部分
                if(cur.val<x){ // 前半部分
                    if(bs == null){
                        // 存放第一个节点
                        bs = cur;
                        be = cur;
                      //  cur = cur.next;
                    }else{
                        be.next = cur ;
                        be = be.next;
                       // cur = cur.next;
                    }
                }else{ // 后半部分
                    if(as == null){
                        // 存放第一个节点
                        as = cur;
                        ae = cur;
                       // cur = cur.next;
                    }else{ //尾插
                        ae.next = cur ;
                        ae = ae.next;
                       // cur = cur.next;

                    }
                }
                cur = cur.next;
            }
            // 走到这里的时候说明原来的链表已经遍历完了
            // 然后链接这两个链表

           /* be.next = as;
            ae.next = null;
            return bs;*/ //返回头节点bs

            //但是有一个问题就是不能保证全部数据都是小于x
            // 或者全部数据都是大于等于x的
            // 就是有可能第一个段没有数据或者第二个段没有数据
            // 所以要先判断一下

            if(bs!=null){
                //第一个段不为null
                be.next = as;
            }else{
                //没有第一段
                return  as;
            }
            //第二个段的问题
            if(as!=null){
                ae.next = null;
            }
            return bs;
        }

        //输入两个链表找出他们的第一个公共节点
         // 相交不相交是靠地址决定的

        // 当两个链表的长度相同时
        // 定义两个节点，让这两个节点同时走
        // 当两个节点长度不同时
        // 先看长度差几个，然后再让长的链表先走相差的呢几步

        //问题。你怎么知道哪个链表长？
        // 你怎么判断相遇？是两个引用
        // headA == headB 么？
        //  在main函数里面写


        //链表为环
    // 判断链表中是否有环
    // 用快慢指针，这样才可以判断相遇
    // 只能是走两步走一步，不能是走三步走两步因为这种是有可能永远不相遇的
    // 因为走一步走两步最多只差一个环的长度
    // 就是数学上的追击问题

    public boolean hasCycle(){
            Node fast = head;
            Node slow = head;
            while(fast != null && fast.next!=null){
                fast = fast.next.next;
                slow = slow.next;
                if (fast == slow){
                    return true;
                }
            }
            return false;
    }

     //判断环的入口点
      // 分析图片在电脑的文件上
    public Node FirstLoopExit(){
            //先判断是否相遇点
        Node fast = head;
        Node slow = head;
        while(fast != null && fast.next!=null){
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow){
                break;
            }
        }
       if(fast == null || fast.next==null){
           return null;
       }
       //如果有环 那么接下来找出第一个节点
        slow = head;
       while(fast != slow){
           slow = slow.next;
           fast = fast.next;
       }
       return slow;
    }

// 在编译器里面测试的话先要创造一个的环
 public void createLoop(){
            Node cur = head;
            while(cur.next != null){
                cur = cur.next;
            }
            cur.next = head.next.next;
    }

    }

